package jianzhiOffer;
//剑指 Offer 68 - II. 二叉树的最近公共祖先
public class Num68_II_lowestCommonAncestor {
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 找到p和q的所有祖先
        findNode(root,p,q);
        return lca;


    }
    //找祖先
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return false;
        }
        int left = findNode(root.left, p, q) ? 1 : 0;
        int right = findNode(root.right, p, q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid == 2){
            lca = root;
        }
        return (left + mid +right) > 0;
    }


}
